class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        left_index = 0
        right_index = len(nums) - 1
        while right_index - left_index >= 2:
            mid_index = int((right_index + left_index) / 2)
            if nums[mid_index] == target:
                return True
            else:
                if nums[left_index] == nums[mid_index] == nums[right_index]:
                    left_index += 1
                    right_index -= 1
                else:
                    if nums[right_index] > nums[mid_index]:
                        if nums[mid_index] < target <= nums[right_index]:
                            left_index = mid_index + 1
                        else:
                            right_index = mid_index - 1
                    else:
                        if nums[right_index] < nums[mid_index]:
                            if nums[left_index] <= target < nums[mid_index]:
                                right_index = mid_index - 1
                            else:
                                left_index = mid_index + 1
                        else:
                            if nums[left_index] > nums[mid_index]:
                                right_index = mid_index - 1
                            else:
                                if nums[left_index] <= target < nums[mid_index]:
                                    right_index = mid_index - 1
                                else:
                                    left_index = mid_index + 1
        if nums[left_index] == target or nums[right_index] == target:
            return True
        else:
            return False


data = Solution()
nums = [1,0,1,1,1]
target = 0
print(data.search(nums, target))
